package com.isaiah.map;

/**
 * @Title: 基于链表实现的Map实现
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/5/2513:35
 */
public class LinkedListMap<K extends Comparable<K>, V> implements Map<K, V> {
    /**
     * 定义链表节点
     */
    private class Node{
        private K key;
        private V value;
        private Node next;

        public Node(K key, V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public Node(K key){
            this(key, null, null);
        }
        public Node(){
            this(null, null, null);
        }
    }

    private Node dummyHead;

    private int size;

    public LinkedListMap() {
        this.dummyHead = new Node();
        this.size = 0;
    }



    @Override
    public void add(K key, V value) {
        Node node = this.getNode(key);
        if (node == null){
            // 在链表边头添加一个新节点
            this.dummyHead.next = new Node(key, value, dummyHead.next);
        }else{
            node.value = value;
        }
    }

    @Override
    public V remove(K key) {
        // 遍历节点, 找出key相等的节点
        Node current = this.dummyHead;
        while (current.next != null){
            if (current.next.key.equals(key)){
                break;
            }
            current = current.next;
        }
        // 删除查找到的节点
        if (current.next != null){
            // 保存要删除的节点到一个变量
            Node delNode = current.next;
            // 将当前节点的next指向要删除节点的next（断开要删除的节点）
            current.next = delNode.next;
            // 要删除的节点的next指向置空
            delNode.next = null;
            // 维护size
            this.size--;
            return delNode.value;
        }
        return null;
    }

    @Override
    public boolean contains(K key) {
        return getNode(key) != null;
    }

    @Override
    public V get(K key) {
        // 1. 根据key找到Node
        Node node = this.getNode(key);
        // 2. 返回node中的value
        return node == null ? null : node.value;
    }

    private Node getNode(K key) {
        // 遍历链表，逐一判断如果遍历的节点key等于要查找的key，则返回当前遍历的节点
        Node current = dummyHead.next;
        while (current != null){
            if (current.key.equals(key)){
                return current;
            }
            current = current.next;
        }
        return null;
    }


    @Override
    public void set(K key, V value) {
        // 1. 根据key查找节点
        Node node = getNode(key);
        if (node == null){
            throw new IllegalArgumentException(key + "doesn't exist!");
        }
        // 2. 更新节点的value
        node.value = value;

    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }
}
